package org.algorithm.biubiu.wheel_1.数组.三月.第二周;

import java.util.Arrays;

/**
 * @author biubiu
 * @date 2022/03/08 11:38 PM
 * @description:        周四作业
 *
 *  <p>
 *      给你一个整数数组 nums 和一个整数 k 。请你向 nums 中追加 k 个 未 出现在 nums 中的、互不相同 的 正 整数，并使结果数组的元素和 最小 。
 *
 *      返回追加到 nums 中的 k 个整数之和。
 *
 *      案例：
 *          输入：nums = [1,4,25,10,25], k = 2
 *          输出：5
 *          解释：在该解法中，向数组中追加的两个互不相同且未出现的正整数是 2 和 3 。
 *          nums 最终元素和为 1 + 4 + 25 + 10 + 25 + 2 + 3 = 70 ，这是所有情况中的最小值。
 *          所以追加到数组中的两个整数之和是 2 + 3 = 5 ，所以返回 5 。
 *  </p>
 *
 * uri:  https://leetcode-cn.com/problems/append-k-integers-with-minimal-sum/
 */
public class 向数组中追加K个整数 {

    public static void main(String[] args) {
        int[] nums = {1,4,25,10,25};
        System.out.println(minimalKSum(nums, 2));
    }


    public static long minimalKSum(int[] nums, int k) {
        if (nums == null) return -1;
        Arrays.sort(nums);
        int start = 1;
        int sum = 0;

        for (int i = 0; i < nums.length && k > 0; ++i) {
            if (start < nums[i]) {
                //计算 当前区间可以累加的数量
                int count = Math.min(nums[i] - start, k);
                //求和 (why start+count-1 ？？？因为 每次循环的时候start 已经+1)
                sum += (start-1 + start+count) * count/2;
                k -= count;
            }
            start = nums[i] + 1;
        }
        if (k > 0) {
            //k>0 && 当前应该添加的元素已经大于数组的最后一个元素 继续+1
            sum += (start + start + k - 1) * k / 2;

        }
        return sum;
    }
}
